package 复杂度要求;

public class 相邻最大差值桶排序应用 {

	public static void main(String[] args) {

	}

	public static int findMaxDivision(int[] A, int n) {
		int maxnum = A[0];
		int minnum = A[0];

		// 查找最大值和最小值
		for (int i = 0; i < A.length; i++) {
			maxnum = Math.max(maxnum, A[i]);
			minnum = Math.min(minnum, A[i]);
		}

		// 生成桶+填桶
		int[] arr = new int[maxnum - minnum + 1];
		for (int i = 0; i < A.length; i++) {
			arr[A[i] - minnum]++;
		}

		int count = 0;
		int max = 0;
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] == 0) { // 桶为空
				count++; // 记录连续空桶数
			} else {
				max = Math.max(max, count);
				count = 0;
			}
		}
		return max + 1; // 如最大值为9，最小值为3，中间有5个空桶，但差值应为6
	}
}
